package leetcode.每日一题;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author ：zsy
 * @date ：Created 2022/10/13 11:10 AM
 * @description：
 */
public class 最多能完成排序的块 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.maxChunksToSorted(new int[]{1,0,2,3,4}));
    }

    /*class Solution {
        public int maxChunksToSorted(int[] arr) {
            int len = arr.length;
            if (len == 0) return 0;
            int[] sortedArr = Arrays.copyOf(arr, len);
            Arrays.sort(sortedArr);
            Set<Integer> set = new HashSet<>();
            set.add(sortedArr[0]);
            int idx = 1;
            int ans = 1;
            for (int a : arr) {
                if (set.size() == 0) {
                    set.add(sortedArr[idx++]);
                    ans++;
                }
                while (!set.contains(a)) {
                    set.add(sortedArr[idx++]);
                }
                set.remove(a);
            }
            return ans;
        }
    }*/

    class Solution {
        public int maxChunksToSorted(int[] arr) {
            int ans = 0;
            int m = 0;
            for (int i = 0; i < arr.length; i++) {
                m = Math.max(m, arr[i]);
                if (m == i) {
                    ans++;
                }
            }
            return ans;
        }
    }
}
